เมนูนำทาง
วิธีการครอส-เอนโทรปี
ในกรณีที่เราพยายามที่จะใช้วิธีครอส-เอนโทรปีเพื่อประมาณค่านั้น สามารถแปลงปัญหาเป็นสมการคณิตศาสตร์ของการประมาณหาค่าคาดหวังง่ายๆได้ดังสมการที่ (1)
ℓ = E f [ H ( X ) ] = ∫ H ( x ) f ( x ) d x {\displaystyle \ell =\mathbb {E} _{f}[H(X)]=\int H(x)f(x)\,dx} (1)เมื่อ H คือฟังก์ชันที่เราต้องการประมาณค่า เรียกได้อีกอย่างหนึ่งว่า ฟังก์ชันของประสิทธิภาพของตัวอย่างสุ่ม
และ f คือฟังก์ชันของความหนาแน่นของความน่าจะเป็นของตัวแปรสุ่ม X
ซึ่งสำหรับวิธีการประมาณค่า l {\displaystyle l} ในสมการที่ 1 นั้น ในกรณีที่สามารถสุ่มตัวอย่างสุ่มด้วยความหนาแน่นของความน่าจะเป็น f ( x ) {\displaystyle f(x)} ได้ยาก จะทำการสร้างฟังก์ชัน f ( x ) {\displaystyle f(x)} เพื่อที่จะสามารถประมาณค่าได้ง่ายขึ้นตามสมการที่ 2
ℓ = ∫ H ( x ) f ( x ) g ( x ) g ( x ) d x = E g [ H ( x ) f ( x ) g ( x ) ] {\displaystyle \ell =\int H(x){\frac {f(x)}{g(x)}}g(x)\,dx=\mathbb {E} _{g}[H(x){\frac {f(x)}{g(x)}}]} (2)โดยที่กำหนดให้
g ( x ) = 0 {\displaystyle g(x)=0\,} เมื่อ H ( x ) f ( x ) = 0 {\displaystyle H(x)f(x)=0\,}เนื่องจาก g เป็นความหนาแน่นของความน่าจะเป็นที่เราเป็นคนสร้างขึ้น ทำให้การสุ่มตัวอย่างเป็นไปได้ง่ายกว่า f ดังนั้น เราจึงสามารถสุ่มตัวอย่างสุ่ม X 1 , . . . , X N {\displaystyle X_{1},...,X_{N}} ตามความหนาแน่นของความน่าจะเป็นของ g(x) ได้ง่ายกว่า ทำให้ประมาณค่าของ l ด้วยตัวประมาณค่าที่ไม่ลำเอียงได้ง่ายขึ้นตามสมการที่ (3)
ℓ ^ = 1 N ∑ k = 1 N H ( X k ) f ( X k ) g ( X k ) {\displaystyle {\widehat {\ell }}={\frac {1}{N}}\sum _{k=1}^{N}H(X_{k}){\frac {f(X_{k})}{g(X_{k})}}} (3)จากปัญหาการประมาณค่า ก็จะเหลือแค่ปัญหาว่าจะสร้างความหนาแน่นของความน่าจะเป็น g ที่ดีที่สุดได้อย่างไรซึ่งค่า g ที่ดีที่สุดในอุดมคตินั้นนิยามด้วย
g ∗ ( x ) α | H ( x ) | f ( x ) {\displaystyle g^{*}(x)\alpha |H(x)|f(x)\,}แต่สิ่งที่เกิดขึ้นก็คือ เราสามารถหาค่า g*(x) ได้ยาก สำหรับวิธีครอส-เอนโทรปีนี้แทนที่จะมุ่งไปที่การหาค่าของ g*(x) จะพยายามหาค่าของ g ที่ทำให้ความแตกต่างระหว่าง g และ g* น้อยที่สุด ซึ่งความแตกต่างนั้นเองที่เรียกว่าครอส-เอนโทรปีตามที่เกริ่นไว้ในช่วงต้น ซึ่งครอส-เอนโทรปีของความหนาแน่นของความน่าจะเป็นของสองฟังก์ชันนั้น นิยามได้ดังสมการที่ (4)
D ( f , g ) = E f [ l n f ( X ) g ( X ) ] = ∫ f ( x ) l n ( f ( x ) ) d x − ∫ f ( x ) l n ( g ( x ) ) d x {\displaystyle D(f,g)=\mathbb {E} _{f}[ln{\frac {f(X)}{g(X)}}]=\int f(x)ln(f(x))dx-\int f(x)ln(g(x))dx} (4)ซึ่งจากสมการที่ (5) R. Y. Rubinstein ได้นำเสนอวิธีสำหรับแก้ปัญหานี้ไว้แล้ว[4]
ในปัญหาเฉพาะที่ชื่อว่าปัญหาการหาความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก(rare event probability) ซึ่งเป็นปัญหาที่ประยุกต์ด้วยวิธีครอส-เอนโทรปีกันอย่างแพร่หลาย โดยเป็นกรณีเฉพาะที่ฟังก์ชัน H เป็นฟังก์ชันตัวชี้ของฟังก์ชัน S ( x ) {\displaystyle S(x)} วัดที่ระดับ γ {\displaystyle \gamma } ตามสมการ H ( x ) = I S ( X ) ≥ γ {\displaystyle H(x)=I_{S(X)\geq \gamma }} ซึ่งในการประมาณค่าของ ℓ {\displaystyle \ell } ด้วยวิธีเดิมเพื่อหาความน่าจะเป็นที่ S ( x ) ≥ γ {\displaystyle S(x)\geq \gamma } นั้นจะยากโดยดูได้จากสมการที่ (5) คือค่าของ H ( X k ) {\displaystyle H(X_{k})} ส่วนมากจะมีค่าเป็น 0 ไปมากพอสมควรจะไม่สามารถประมาณหาค่าที่แม่นยำได้ วิธีการแก้ไขคือต้องทำวิธีการ ครอส-เอนโทรปีหลายๆรอบ หลายๆชั้น โดยจะปรับค่าพารามิเตอร์ v และระดับปัจจุบันให้เข้าใกล้ v* และ γ {\displaystyle \gamma } ไปเรื่อยๆจนถึงเงื่อนไขยุติที่พอใจ สามารถเขียนขั้นตอนวิธีตามที่ได้อธิบายมาเป็นรหัสเทียมได้ดังนี้
1 v ^ 0 = u {\displaystyle {\widehat {v}}_{0}=u} และ 2 N e = ⌈ ρ N ⌉ {\displaystyle N^{e}=\lceil \rho \,N\rceil } 3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม X 1 , . . . , X N {\displaystyle X_{1},...,X_{N}\,} ตามความหนาแน่นของความน่าจะเป็น f ( − : v ^ t − 1 ) {\displaystyle f(-:{\widehat {v}}_{t-1})\,} 8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 S ( i ) = S ( X i ) {\displaystyle S_{(i)}=S(X_{i})\,} 10 เรียงลำดับจากน้อยไปหามาก(S) 11 γ ^ t = S ( N − N e + 1 ) {\displaystyle {\widehat {\gamma }}_{t}=S_{(N-N^{e}+1)}\,} 12 γ ^ t {\displaystyle {\widehat {\gamma }}_{t}\,} = ค่าต่ำสุด( γ {\displaystyle \gamma \,} , γ ^ t {\displaystyle {\widehat {\gamma }}_{t}} )13 คำนวณ v ^ t {\displaystyle {\widehat {v}}_{t}} จากสมการ (5) ด้วย X 1 , . . . , X N {\displaystyle X_{1},...,X_{N}} และ w = v ^ t − 1 {\displaystyle w={\widehat {v}}_{t-1}} 14 ระหว่างที่ γ ^ t < γ {\displaystyle {\widehat {\gamma }}_{t}<\gamma } 1516 สุ่มตัวอย่างสุ่ม X 1 , . . . , X N 1 {\displaystyle X_{1},...,X_{N_{1}}\,} ตามความหนาแน่นของความน่าจะเป็น f ( − : v ^ t ) {\displaystyle f(-:{\widehat {v}}_{t})} 17 คำนวณ ℓ {\displaystyle \ell } จากสมการ (3) ด้วย X 1 , . . . , X N 1 {\displaystyle X_{1},...,X_{N_{1}}\,} 18 คืนค่า ℓ {\displaystyle \ell } จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า v ^ 0 , N , ρ {\displaystyle {\widehat {v}}_{0},N,\rho } ให้เหมาะสมกับความต้องการ ซึ่งโดยปกติ ρ {\displaystyle \rho } จะมีค่าอยู่ระหว่าง 0.01 และ 0.1 และค่าของ N {\displaystyle N} จะน้อยว่า N 1 {\displaystyle N_{1}} มากๆ เช่น N = 10000 {\displaystyle N=10000} ในขณะที่ N 1 = 100000 {\displaystyle N_{1}=100000} และขั้นตอนวิธีนี้จะรับประกันว่าสามารถทำงานจนจบได้แน่นอนหากค่าของ ρ {\displaystyle \rho } มีค่าเล็กมากพอ
เมนูนำทาง
วิธีการครอส-เอนโทรปีใกล้เคียง
แหล่งที่มา
WikiPedia: วิธีการครอส-เอนโทรปี